package com.sakura;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Code18_四数之和 {

    public static void main(String[] args) {
        int[] nums = {2,2,2,2,2};
        System.out.println(new Code18_四数之和().fourSum(nums, 8));
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        ArrayList<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                long tag = (long) target - nums[i] - nums[j];
                int L = j + 1;
                int R = n - 1;
                while (L < R) {
                    if (nums[L] + nums[R] == tag) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[L]);
                        list.add(nums[R]);
                        ans.add(list);
                        while (L < R && nums[L] == nums[L + 1]) L++;
                        while (L < R && nums[R] == nums[R - 1]) R--;
                        L++;
                        R--;
                    } else if (nums[L] + nums[R] < tag) {
                        L++;
                    } else {
                        R--;
                    }
                }
            }
        }
        return ans;
    }
}
